#include<iostream>
#include<algorithm>
using namespace std;

// PBMC is always 0
const int MAX_NUM = 510;
const int MAX_INT = (unsigned)(-1)>>1;
int Cm, N, Sp, M;
int v[MAX_NUM], e[MAX_NUM][MAX_NUM];
int visited[MAX_NUM],pl[MAX_NUM];//,num[MAX_NUM];
int pre[MAX_NUM][MAX_NUM]; // use a pre mat to mem all possible pre
// and do a dfs on pre, we can traverse all possible shortest path and find the sol
int path[MAX_NUM],top,aux[MAX_NUM],atop;
// note that you only go along the road, you cannot take surplus bike in behind to front
int send = MAX_INT, fetch = MAX_INT;

void dfs(int id)
{
    aux[atop++] = id;
    if(!id)
    {
        int send_tmp = 0,fetch_tmp = 0;
        for(int i = atop-2;i>=0;--i)
        {
            if(v[aux[i]] > Cm/2)fetch_tmp += (v[aux[i]] - Cm/2);
            else if (v[aux[i]] < Cm/2)
            {
                if(fetch_tmp >= Cm/2-v[aux[i]])fetch_tmp -= (Cm/2 - v[aux[i]]);
                else
                {
                    send_tmp += (Cm/2 - v[aux[i]] - fetch_tmp);
                    fetch_tmp = 0;
                }
            }
        } 
        if(send_tmp < send || (send_tmp==send && fetch_tmp < fetch)) 
        {
            send = send_tmp; fetch = fetch_tmp;
            top = 0;
            for(int i = atop-1;i>=0;--i) path[top++] = aux[i];
        }
        atop--;
        return;
    }
    for(int i=0;i<N+1;++i){if(pre[id][i])dfs(i);}
    atop--;
}

int main(int argc, char const *argv[])
{
    freopen("test.txt","r",stdin);
    cin>>Cm>>N>>Sp>>M;
    for(int i=1;i<=N;++i)cin>>v[i];
    fill(e[0],e[0]+MAX_NUM*MAX_NUM,MAX_INT);
    for(int i=0;i<M;++i)
    {
        int si,sj,t; cin>>si>>sj>>t;
        e[si][sj]=e[sj][si]=t;
    }
    // implement Dijk with dp; start from 0
    fill(pl,pl+N+1,MAX_INT);
    pl[0] = 0; 
    for(int _=0;_<N;++_)
    {
        int id,lmin=MAX_INT;
        for(int i = 0;i<N+1;++i)
        {
            if(!visited[i] && pl[i]<lmin){id = i; lmin = pl[i];}
        }
        visited[id] = 1;
        // do update
        for(int i = 1;i<N+1;++i)
        {
            if(!visited[i] && e[id][i] < MAX_INT && pl[id]+e[id][i]<=pl[i])
            {
                if(pl[id] + e[id][i] < pl[i])
                {
                    pl[i] = pl[id]+e[id][i];
                    fill(pre[i],pre[i]+N+1,0);
                }
                pre[i][id] = 1;
            }
        }
    }
    // do a dfs on pre, and get num and path we need
    // may need a recursive way to fix this
    dfs(Sp);
    cout<<send<<" ";
    cout<<0;
    for(int i = 1;i<top;++i)cout<<"->"<<path[i];
    cout<<" "<<fetch;
    
    return 0;
}
